There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Example 1:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph is shown. The cheapest price from city0to city2with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph is shown. The cheapest price from city0to city2with at most 0 stop costs 500, as marked blue in the picture.
Constraints:
1 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dst
Average Rating: 3.46 (105 votes)
Solution
Approach 1: Dijkstra's Algorithm
Intuition
If we forget about the part where the number of stops is limited, then the problem simply becomes the shortest path problem on a weighted graph, right? We can treat this as a graph problem where:
- the cities can be treated as nodes in a graph
- the connections between each of the cities can be treated as the edges and finally
- the cost of going from one city to another would be the weight of the edges in the graph.
It's important to model the problem in a way that standard algorithms or their slight variations can be used for the solutions. Whenever we have a problem where we're given a bunch of entities and they have some sort of connections between them, more often than not it can be modeled as a graph problem. Once you've figured out that the question can be modeled as a graph problem, you then need to think about the various aspects of a graph i.e.
- directed vs undirected
- weighted vs unweighted
- cyclic vs acyclic
These aspects will help define the algorithm that you can consider for solving the problem at hand. For example a standard rule of thumb that is followed for solving shortest path problems is that we mostly use Breadth-first search for unweighted graphs and use Dijkstra's algorithm for weighted graphs. An implied condition to apply the Dijkstra's algorithm is that the weights of the graph must be positive. If the graph has negative weights and can have negative weighted cycles, we would have to employ another algorithm called the Bellman Ford's. The point here is that the properties of the graph and the goal define the kind of algorithms we might be able to use.
Coming back to the original statement at the beginning of the article. If we don't consider the part where the number of stops is limited, this problem becomes a standard shortest paths problem in a weighted graph with positive weights and hence, it becomes a prime candidate for Dijkstra's. As we all know, Dijkstra's uses a min-heap (priority queue) as the main data structure for always picking out the node which can be reached in the shortest amount of time/cost/weight from the current point starting all the way from the source. That approach as it is won't work out for this problem.
First of all, we need to keep track of the number of stops taken to reach a node (city), in addition to the shortest path from the source node. This is important because if at any point we find that we have exhausted K stops, we can't progress any further from that node because the number of stops are bounded by the problem. Let's consider a simple example and run through it with the basic Dijkstra's algorithm and see why we might run into a problem with the off-the-shelf code i.e. Dijkstra's without any modifications.
Now suppose that we want to go from the source node A in the graph above to the destination node E via the cheapest possible route with at most 2 stops. Let's ignore the number of stops for now and see how the usual Dijkstra would unfold and pick the nodes. So first of all, we will consider the neighbors of the source node and add them to our min-heap. Next, we will pick the element with the current shortest distance which would be D with a value of 5 as opposed to B with 7.
Moving on, the next node that will be picked is B since it has the current shortest distance from the source. Let's see what the heap looks like once we pick B and process its neighbors. Note that according to the algorithm, once a node has been processed i.e., once a node is popped from the min-heap, we never consider that node again in some other node's neighbors i.e., we never add it again to the heap down the line. This is because of the greedy nature of the algorithm. When a node is removed from the heap, it is guaranteed that the distance from the source at that point is the shortest distance. The processed nodes are marked in blue in the figures here.
Moving on, the algorithm will pick C and its neighbor E will be added into the heap. You'll notice that there are two nodes containing the city E which is fine since E hasn't been processed yet and this just means there are multiple paths of reaching E.
Next, we will remove the node E with a distance of 12 from the source and 3 stops from the source. At this point, we cannot go any further i.e. we cannot consider its neighbor because We have already exhausted the number of stops in this example. So, we don't add the neighbor which also happens to be the destination node to the heap. The only node left in the heap is E with a distance of 15 from source and 2 stops from the source.
Here's the problem now. We will not consider this node because we have already processed the node
Ein the previous step. Clearly, the distance15is greater than12. So Dijkstra's will discard this heap node and the algorithm will finish, without ever reaching the destination!
The thing we need to modify here is that we need to re-consider a node if the distance from the source is shorter than what we have recorded. So we won't change the min-heap's priority which is to pick nodes with the shortest distance from the source. However, if we ever encounter a node that has already been processed before but the number of stops from the source is lesser than what was recorded before, we will add it to the heap so that it gets considered again! That's the only change we need to make to make Dijkstra's compliant with the limitation on the number of stops.
Algorithm
-
Initialize a min-heap or a priority queue. Let's call it
Hfor our algorithm. -
We will need a couple of arrays here. One would be for maintaining the shortest distances of each node from the source and another one would be for maintaining the shortest number of stops from the source.
-
Next, we need to convert the input into an adjacency matrix format. So, we will process the given input and build an adjacency matrix out of it.
-
Add (source,0,0) into the heap. The middle value represents the current shortest distance from the source and the last value represents the current minimum number of stops from the source to reach this node.
-
We assume that these values for all the other nodes in the graph are
inf. -
We continue processing the nodes until either of the following conditions are met:
- We reach the destination node or
- We exhaust the heap which would mean we were not able to reach the destination at all.
-
At each step, we remove a node from the heap i.e.
ExtractMinoperation on the min-heap. This would represent the node with the shortest distance from the source amongst the ones in the heap. Let's call this nodeC. -
We iterate over all of
C'sneighbors which we can obtain from our adjacency matrix. For each neighbor, we check if the value dC+WC, V is less than dV where V represents the neighbor node, dC and dV represent the shortest distances (from the dictionary) of these nodes from the source and finally, WC, V represents the weight (cost of the flight) from node (city) C to V. -
If this is not the case then we check if number of stops for node C
+ 1is lower than the number of stops for the node V (from the other dictionary). If that is the case, then it means there is a path from the source to the node V which is slightly expensive than what we have right now, but it has lesser stops and hence, it should be considered. -
If either of the two conditions above are satisfied, we add the node V to the heap with updated distance and number of stops. In any case, we will update the corresponding dictionary as well.
Complexity Analysis
-
Time Complexity: Let E represent the number of flights and V represent the number of cities. The time complexity is mainly governed by the number of times we pop and push into the heap. We will process each node (city) atleast once and for each city popped from the queue, we iterate over its adjacency matrix and can potentially add all its neighbors to the heap. Thus, the time taken for extract min and then addition to the heap (or simply, heap replace) would be O(V2⋅log V).
- Let's talk a bit more about the implementation of Dijkstra's here. The traditional algorithm is not exactly written the way we've explained above.
- The traditional algorithm adds all the nodes into the heap with the source having a distance value of
0and all others having a valueinf. - When we process the neighbors of a node and find that a particular neighbor can be reached in a shorter distance (or lesser number of stops), we update its value in the heap. In our implementation, we add a new node with updated values rather than updating the value of the existing node. To do that, we will need another dictionary that will probably keep the index location for a node in the heap or something like that. This would be necessary because a heap is not a binary search tree and it doesn't have any search properties for quick search and updates.
- If we keep the number of nodes in the heap fixed to V, then the complexity would be O((V+E)⋅log V). Granted, in our case, the heap might contain more than V nodes at some point due to the same city being added multiple times. Therefore, the complexity would be slightly more. That is not being accounted for here since that is an implementation detail and not necessary for the algorithm we discussed here.
- Yet another point to keep in mind here is that we are using an adjacency matrix rather than adjacency list here. The typical Dijkstra's algorithm would use an adjacency list and that brings down the complexity slightly because you don't "check" if a connection exists or not unlike in adjacency matrix. However, since the number of nodes are very less for this problem, we preferred to take the route of adjacency matrix as that gives us sequential access to elements and leads to speed-ups due to cache localization.
-
Space Complexity: O(V2) is the overall space complexity. O(V) is occupied by the two dictionaries and also by the heap and V2 by the adjacency matrix structure. As mentioned above, there might be duplicate cities in the heap with different distances and number of stops due to our implementation. But we are not taking that into consideration here. This is the space complexity of the traditional Dijkstra's and it doesn't change with the algorithm modifications (not the implementation modifications) we've done here.
Approach 2: Depth-First-Search with Memoization
Intuition
This problem can easily be modeled as a dynamic programming problem on graphs. What does a dynamic programming problem entail?
- It has a recursive structure.
- A bunch of choices to explore at each step.
- Use the optimal solutions for sub-problems to solve top-level problems.
- A base case.
This problem fits the bill. We have a dedicated start and endpoint. We have a bunch of choices for each node in the form of its neighbors. And, we want to minimize the overall shortest distance from the source to the destination which can be represented as a recursive structure in terms of shortest distances of its neighbors to the destination. So, we can apply a dynamic programming approach to solve this problem. We'll look at a recursive implementation here with memoization first and then talk about the iterative approach as well.
As with any recursive approach, we need to figure out the state of recursion. There are two parameters here which will control our recursion. One is obviously the node itself. The other is the number of steps. Let's call our recursion function recurse and define what the state of recursion looks like. recurse(node,stops) will basically return the shortest distance for us to reach the destination from node considering that there are stops left. This being said, it's easy to figure out what the top-level problem would be. It would be recurse(0,K).
Let's consider the following graph to understand why memoization (or caching) is required here.
Say we start the source node A and build our recursion tree from there. There are two possible routes of getting to the node C with exactly 2 stops. Let's look at what these are.
While the cost of these two paths is different, once we are at the node C, we have 2 steps less than what we had when we started off from the source node A. Our recursion representation doesn't care about the path you took to get to a node. It is about the shortest (cheapest) path from the current node with the given number of steps to get to a destination. In that sense, both these scenarios are exactly the same because both lead us to the same recursion state which is (recurse(C,K-2)) and hence, the result for this recursion state can be cached or memoized.
Algorithm
-
We'll define a function called
recursewhich will take two inputs:nodeandstops. -
We'll also define a dictionary
memoof tuples that will store the optimal solution for each recursion state encountered. -
At each stage, we'll first check if we have reached the destination or not. If we have, then no more moves have to be made and we return a value of
0since the destination is at a zero distance from itself. -
Next, we check if we have any more stops left. If we don't then we return
infbasically representing that we cannot reach the destination from the current recursion state. -
Finally, we check if the current recursion state is cached in the
memodictionary and if it is, we return the answer right away. -
If none of these conditions are met,we progress in our recursion. For that we will iterate over the adjacency matrix to obtain the neighbors for the current node and make a recursive call for each one of them. The
nodewould be the neighboring node and the number of stops would incremeneted by1. -
To each of these recursion calls, we add the weight of the corresponding edge i.e.
recurse(neighbor, stops + 1) + weight(node, neighbor)
-
We need to return the result of
recurse(src, 0)as the answer.
Complexity Analysis
- Time Complexity: The time complexity for a recursive solution is defined by the number of recursive calls we make and the time it takes to process one recursive call. The number of recursive calls we can
potentiallymake is O(V⋅K). In each recursive call, we iterate over a given node's neighbors. That takes time O(V) because we are using an adjacency matrix. Thus, the overall time complexity is O(V2⋅K). - Space Complexity: O(V⋅K+V2) where O(V⋅K) is occupied by the
memodictionary and the rest by the adjacency matrix structure we build in the beginning.
Approach 3: Bellman-Ford
Intuition
Let's look at the official definition of the Bellman-Ford algorithm straight from Wikipedia:
Like Dijkstra's algorithm, Bellman-Ford proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance and is replaced by the minimum of its old value and the length of a newly found path.
However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman-Ford algorithm simply relaxes all the edges and does this ∣V∣−1 times, where ∣V∣ is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually, all vertices will have their correct distances. This method allows the Bellman-Ford algorithm to be applied to a wider class of inputs than Dijkstra.
The term relax an edge simply means that for a given edge U -> V we check if dU+WU,V<dV where dU and dV represent the shortest path distances of these nodes from the source right now. To relax an edge means to see if the shortest distance can be updated or not.
An important part to understanding the Bellman Ford's working is that at each step, the relaxations lead to the discovery of new shortest paths to nodes. After the first iteration over all the vertices, the algorithm finds out all the shortest paths from the source to nodes which can be reached with one hop (one edge). That makes sense because the only edges we'll be able to relax are the ones that are directly connected to the source as all the other nodes have shortest distances set to inf initially.
Similarly, after the (K+1)th step, Bellman-Ford will find the shortest distances for all the nodes that can be reached from the source using a maximum of K stops. Isn't that what the question asks us to do? If we run Bellman-Ford for K+1 iterations, it will find out shortest paths of length K or less and it will find all such paths. We can then check if our destination node was reached or not and if it was, then the value for that node would be our shortest path!
Let's quickly look at a couple of iterations of Bellman-Ford on a sample graph to understand how relaxation works and how K+1 iterations can possibly give us our solution. The image below showcases the initial setup before the first iteration of Bellman-Ford is executed.
Let's look at what the graph looks like after a single iteration.
It's important to understand the meaning of what we said in the figure above. We are not saying that after the first iteration we will find the absolute shortest distance from A to B and D. We are just saying that the shortest distance using a single edge only will be found after first iteration. What happens in the next iteration? Well, we will find all the shortest paths that can be reached from the source by using at-most 2 edges. In this example, since the values for nodes B and D were updated in the previous iteration, they will be re-used in the next iteration to relax edges B -> E, B -> C, and D -> C.
Isn't that what Dynamic Programming is all about......
Well, yes! Using the optimal solutions to sub-problems to find optimal solutions to bigger problems. We use the optimal solutions to shortest paths using 1 edge to find shortest paths using 2 edges and so on.
We'll go one final iteration here since this is where things get interesting and this will bring some more clarity. The node E was discovered in the second iteration and we have the value 15 corresponding to it. However, one of the incoming edges C -> E wasn't relaxed in the second iteration because C was also discovered during that iteration. Now that we have a non-infinite value associated with C, we can use it to relax the edge C -> E and that leads to an even shorter path from A ... E!
Another important thing to note about this algorithm is that we don't need to build an adjacency matrix. This algorithm simply iterates over the edges of the graph and that information is already available in the input for the program. So we save on space there as opposed to other algorithms which we've seen.
Algorithm
-
We have a loop that does
K + 1iterations. The plus one is because we need to find the cheapest flight route with at mostKstops in between. That translates toK + 1edges at most. -
In each iteration, we loop over all the edges in the graph and try to relax each one of them. Again, note that the edges or the flights are already given to us in the input and don't need to build any kind of adjacency list or matrix structure which is otherwise standard for other graph algorithms.
-
After
K + 1iterations, we check if the destination has been reached or not. If it's been discovered, then the distance at that point will be the shortest using at mostK + 1edges. -
We use an array to store the current shortest distances of each node from the source. This is possible because the number of nodes is less and we don't need to use a dictionary here. However, a single array is not sufficient here because any values updated in a particular iteration cannot be used to update other values in the same iteration. Thus, we need another distance array which will kind of server as
values in the previous iteration. So we essentially use 2 arrays of size V and we swap between them in each iteration i.e.Iteration-0 ---- Array-1 is the main array Array-2 becomes the previous array Iteration-1 ---- Array-2 is the main array Array-1 becomes the previous array
Let's look at how the two arrays look like at the start of the first iteration. We'll take a look at a couple of iterations so that the it's easier to understand the implementations.
We discovered two new vertices which are directly connected from the source and their corresponding distances were updated accordingly.
Now let's look at how the two arrays would look like at the start of the second iteration. Now the roles would be reversed. The current array in the previous iteration now servers as the previous array.
Notice how the two arrays have swapped roles. You might be thinking that even though the red array is the current one, it doesn't have the latest values 7 and 5. Well, they will be used for the calculation of distance of node C and also, they will be copied over (re-calculated again due to the node A in previous array). Let's see how the two arrays look after the second iteration is complete.
Complexity Analysis
- Time Complexity: O(K⋅E) since we have K+1 iterations and in each iteration, we go over all the edges in the graph.
- Space Complexity: O(V) occupied by the two distance arrays.
Approach 4: Breadth First Search
Intuition
We say that the breadth-first search is a good algorithm to use if we want to find the shortest path in an undirected, unweighted graph. The claim for BFS is that the first time a node is discovered during the traversal, that distance from the source would give us the shortest path. The same cannot be said for a weighted graph. For a weighted graph, there is no correlation between the number of edges composing the path and the actual length of the path which is composed of the weights of all the edges in it. Thus, we cannot employ breadth-first search for weighted graphs.
Breadth-first search has no way of knowing if a particular discovery of a node would give us the shortest path to that node. And so, the only possible way for BFS (or DFS) to find the shortest path in a weighted graph is to search the entire graph and keep recording the minimum distance from source to the destination vertex.
That being said, Breadth-first search is actually a great algorithm of choice for this problem because the number of levels to be explored by the algorithm is bounded by K
The number of levels that the search would go to is limited by the value K+1 in the question. So essentially, we would be trying to find the shortest path, but we won’t have to explore the entire graph as such. We will just go up to the level K+1 and we just need to return the shortest path to the destination (if reachable by level K+1) at the end of the algorithm.
An important consideration here is the size of the queue. We need to control it somehow otherwise, even at very small depths, the graph could grow exponentially. For this very problem however, we will be able to bound the size of a given level (and hence the queue) by V, the number of vertices in the graph. Let's think about what it means to encounter the same node multiple times during breadth first traversal.
Since we will be going only till the level K+1, we don't really have to worry about the number of stops getting exhausted or something. So if the number of stops are out of the way, the only way we will consider adding a node again to the queue is if we found a shorter distance from the source than what we already have stored for that node. If that is not the case then on encountering a node again during the traversal, we can safely discard it i.e not add it to the queue again.
Since this is weighted graph, we cannot assume anything about the shortest distance from source to a node when its first discovered after being popped from the queue. We will have to go to all the K+1 levels and once we've exhausted K+1 levels, we can be sure that the shortest distances we have are the "best" we can find with K+1 edges or less.
Algorithm
- This is standard BFS and we'll be using a queue here. Let's call it
Q. - We'll need a dictionary to keep track of shortest distances from the source. An important thing to note in this approach is that we need to keep a dictionary with the
node, stopsas the key. Basically, we need to keep track of the shortest distance of a node from the source provided that it takesstopsstops to reach it. - Add the source node to the queue. There are multiple ways of tracking the level of a node during breadth-first traversal. We'll be using the size of the queue at the beginning of the level to loop over a particular level.
- We iterate until we exhaust the queue or
K+1levels whichever comes first. - For each iteration, we pop a node from the queue and iterate over its neighbors which we can get from the adjacency matrix.
- For each of the neighbors, we check if the current edge improves that neighbor's shortest distance from source or not. If it does, then we update the shortest distance dictionary (array) accordingly and also add the neighbor to the queue.
- We continue doing this for until one of our terminal conditions are met.
- We will also maintain an
ansvariable to track the minimum distance of the destination from the source. At each step, whenever we update the shortest distance of a node from source, we check if that node is the destination and if it is, we will update theansvariable accordingly. - At the end, we simply check if we were able to reach the destination node by looking at the
ansvariable's value. If we did reach it, then the recorded distance would be the shortest in underKhops (orK + 1edges at most).
Complexity Analysis
- Time Complexity: O(E⋅K) since we can process each edge multiple times depending upon the improvement in the shortest distances. However, the maximum number of times an edge would be processed is bounded by K + 1 since that's the number of levels we are going to explore in this algorithm.
- Space Complexity: O(V2+V⋅K). The first part is the standard memory occupied by the adjacency matrix and in addition to that, the distances dictionary can occupy a maximum of O(V⋅K).
June 2, 2020 3:22 AM
This problem should probably be classified as hard.
Last Edit: August 14, 2020 4:33 AM
Just commenting here for the sake of record keeping. This problem should be marked as hard. In 2020, it is marked as medium. In 2050, when leetcode has 100,000 questions, this question will be marked as easy. Facebook will expect you to solve this in 5 mins with runnable perfect code.
June 24, 2020 1:13 AM
I tried implementing Dijkstra's Algorithm solution in python but on submitting it failed a test case. I tried copy-pasting the solution exactly as is here and it still failed for the test case.
11
[[0,3,3],[3,4,3],[4,1,3],[0,5,1],[5,1,100],[0,6,2],[6,1,100],[0,7,1],[7,8,1],[8,9,1],[9,1,1],[1,10,1],[10,2,1],[1,2,100]]
0
2
4
After tracing through the code several times it seems that the path 0-3-4-1 of cost 9 is never explored because path 0-7-8-9-1 is cheaper (cost 4) and path 0-6-1 has less stops (stops 2, cost 102). Therefore, by the time we get to exploring 4s neighbors, neither if condition is met, and so we don't put it in our pq. So this code says the solution is 0-5-1-10-2 with cost 103 as opposed to the expected solution 11 (0-3-4-1-10-2).
I changed the elif statement to a simple else and the test case passed as well as the submission went through.
I pasted the Approach 1 and submitted but got WRONG ANSWER.
Last Edit: June 9, 2020 6:06 PM
Dijkstra's soln looks really convoluted for some reason. Here a simpler/straightforward implementation.
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
graph = defaultdict(list)
for source,dest,cost in flights: graph[source].append((cost,dest))
heap = []
heapq.heappush(heap,(0,src,-1)) # add src to kick things off
while heap:
nextCost,nextDest,currSteps= heapq.heappop(heap)
if currSteps > K: continue
if nextDest == dst: return nextCost
for nc,nd in graph[nextDest]:
heapq.heappush(heap,(nc+nextCost,nd,currSteps+1))
return -1
Dijkstra's solution posted here does not pass this test case.
11
[[0,3,3],[3,4,3],[4,1,3],[0,5,1],[5,1,100],[0,6,2],[6,1,100],[0,7,1],[7,8,1],[8,9,1],[9,1,1],[1,10,1],[10,2,1],[1,2,100]]
0
2
4
[Expected 11]
July 12, 2020 3:10 PM
What kind of solution article is this. It gives wrong answer for below test case. Did not expect such pathetic quality from official Leetcode solutions. Premium subscription should be made cheaper if I am going to be seeing such cheap stuff.
11
[[0,3,3],[3,4,3],[4,1,3],[0,5,1],[5,1,100],[0,6,2],[6,1,100],[0,7,1],[7,8,1],[8,9,1],[9,1,1],[1,10,1],[10,2,1],[1,2,100]]
0
2
4
for dijkstra solution, in the for loop, while you update the stops[nei], I think it should be stops[nei]=stops+1 instead of stops[nei]=stops; although I tries the two method they both pass all test cases, but I think here while stops means the minstop to reaches the current node you're visiting, while you update stops[nei] you should plus 1 more stop by reaching the neighbor(nei) via current node(node). So it should be "stops+1" instead of "stops". Does anyone else agree with me?
Everything written here should be rechecked thoroughly. Especially the complexity analysis for the Dijkstra and BFS looks incorrect. If you should reconsider a node each time its cheaper path is found, it cannot be O(N) for nodes processing. Also the adjacency matrix for graph storage is less efficient than the adjacency list. If you use the adjacency matrix, you cannot say that even the basic Dijkstra's algorithm works in O((N + E)logN), it's O(N^2logN) as at each iteration we look for node's neighbours among all the nodes.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/21/2021 12:34 | Accepted | 32 ms | 14.8 MB | cpp |
| 06/21/2021 12:33 | Accepted | 24 ms | 14.7 MB | cpp |
| 06/21/2021 12:30 | Accepted | 28 ms | 14.8 MB | cpp |
| 06/21/2021 12:30 | Wrong Answer | N/A | N/A | cpp |
| 06/21/2021 12:26 | Time Limit Exceeded | N/A | N/A | cpp |
| 06/12/2021 20:14 | Accepted | 336 ms | 49.6 MB | cpp |
| 06/12/2021 20:12 | Time Limit Exceeded | N/A | N/A | cpp |
| 06/12/2021 20:11 | Time Limit Exceeded | N/A | N/A | cpp |
| 06/14/2020 13:08 | Accepted | 64 ms | 13 MB | cpp |
x
class Solution {public: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { // source -> (destination, price) vector<vector<pair<int, int>>> v(n); for(int i=0;i<flights.size();i++) { v[flights[i][0]].push_back({flights[i][1], flights[i][2]}); } priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>pq; // city -> maxStops unordered_map<int, int> seen; // {current total price, current source city, max stops to destination allowed} pq.push({0, src, k+1}); while(!pq.empty()) { vector<int> curr = pq.top(); pq.pop(); int currCost = curr[0]; int currCity = curr[1]; int maxStops = curr[2]; // we reached destination if(currCity == dst) return currCost; // we have no more stops left (route not possible) if(maxStops == 0) continue; // if we already visited this city with a greater number of stops left, we skip. if(seen[currCity] >= maxStops) continue; seen[currCity] = maxStops; for(auto it : v[currCity]) { auto [nextCity, price] = it; pq.push({currCost + price, nextCity, maxStops - 1}); } } return -1; }};